// ============================================================================
//
// Graph framework by Aurelien Moreau aurelien.moreau@gmail.com
// Modified by Pierre CHATEL chatelp@gmail.com
// Distributed under LGPL
// Copyright (C) Aurelien Moreau, 2008, 2009. All rights reserved
//
// ============================================================================

package com.thalesgroup.graphFramework.searchMethods;

import java.util.Iterator;

import com.thalesgroup.graphFramework.core.Graph;
import com.thalesgroup.graphFramework.core.Vertex;

public class DepthFirstSearch {
	public static final String colorKey = "searchMethods.DepthFirstSearch.nodeColor";
	public static final String whiteColor = "searchMethods.DepthFirstSearch.whiteNodeColor";
	public static final String greyColor = "searchMethods.DepthFirstSearch.greyNodeColor";
	public static final String blackColor = "searchMethods.DepthFirstSearch.blackNodeColor";
	public static final String foundDateKey = "searchMethods.DepthFirstSearch.nodeFoundDate";
	public static final String processedDateKey = "searchMethods.DepthFirstSearch.nodeProcessedDate";
	public static final String parentKey = "searchMethods.DepthFirstSearch.nodeParent";
	
	private static int globalDate;
	
	/**
	 * Apply Cormen's Depth-First colored search on the following graph.
	 * @param graph the graph to process.
	 * @return true if a cycle has been detected, false if not.
	 */
	public static <S, T> boolean search(Graph<S, T> graph) {
		boolean hasCycle = false;
		
		for(Iterator<Vertex<S, T>> vi = graph.getVertices(); vi.hasNext();) {
			Vertex<S, T> vertex = vi.next();
			vertex.setUserFeature(colorKey, whiteColor);
			vertex.setUserFeature(parentKey, null);
		}
		
		globalDate = 0;
		
		for(Iterator<Vertex<S, T>> vi = graph.getVertices(); vi.hasNext();) {
			Vertex<S, T> vertex = vi.next();
			String vertexColor = (String) vertex.getUserFeature(colorKey);
			if(vertexColor.equals(whiteColor)) {
				hasCycle = visit(vertex, graph) || hasCycle;
			}
		}
		
		return hasCycle;
	}
	
	private static <S, T> boolean visit(Vertex<S, T> vertex, Graph<S, T> graph) {
		boolean hasCycle = false;
		vertex.setUserFeature(colorKey, greyColor);
		vertex.setUserFeature(foundDateKey, ++globalDate);
		
		Vertex<S, T>[] adjacentVertices = graph.getAdjacentVertices(vertex);
		for (Vertex<S, T> adjacentVertex : adjacentVertices) {
			String avColor = (String) adjacentVertex.getUserFeature(colorKey);
			
			//if color is white, node hasn't been already visited
			if(avColor.equals(whiteColor)) {
				adjacentVertex.setUserFeature(parentKey, vertex.getIndex());
				//recurse
				hasCycle = visit(adjacentVertex, graph);
			}
			//if color is grey, we have a cycle
			else if(avColor.equals(greyColor)) {
				hasCycle = true;
			}
		}
		
		vertex.setUserFeature(colorKey, blackColor);
		vertex.setUserFeature(processedDateKey, ++globalDate);
		
		return hasCycle;
	}
}
